
\subsection{\_\_gnu\_pbds :: priority\_queue}

附 ：\href{https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/pq_performance_tests.html#std_mod1}{官方文档地址——复杂度及常数测试}

\begin{cppcode}
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
__gnu_pbds ::priority_queue<T, Compare, Tag, Allocator>
\end{cppcode}

\subsection{模板形参}

\begin{itemize}
\item \texttt{T} : 储存的元素类型
\item \texttt{Compare} : 提供严格的弱序比较类型
\item \texttt{Tag} : 是 \texttt{\_\_gnu\_pbds} 提供的不同的五种堆，Tag 参数默认是 \texttt{pairing\_heap\_tag}
  五种分别是 ：
\begin{itemize}
\item \texttt{pairing\_heap\_tag}：配对堆
官方文档认为在非原生元素 (如自定义结构体 / \texttt{std :: string} / \texttt{pair}) 中，配对堆表现最好
\item \texttt{binary\_heap\_tag}：二叉堆 
官方文档认为在原生元素中二叉堆表现最好，不过我测试的表现并没有那么好
\item \texttt{binomial\_heap\_tag}：二项堆
二项堆在合并操作的表现要优于配对堆  但是其取堆顶元素的
\item \texttt{rc\_binomial\_heap\_tag}：冗余计数二项堆
\item \texttt{thin\_heap\_tag}：除了合并的复杂度都和 Fibonacci 堆一样的一个 tag
\end{itemize}
\item \texttt{Allocator}：空间配置器，由于 OI 中很少出现，故这里不做讲解
\end{itemize}

由于本篇文章只是提供给学习算法竞赛的同学们，故对于后四个 tag 只会简单的介绍复杂度，第一个会介绍成员函数和使用方法。

经作者本机 Core i5@3.1 GHz On macOS 测试堆的基础操作，结合 GNU 官方的复杂度测试，Dijkstra 测试，都表明：

至少对于 OIer 来讲，除了配对堆的其他 4 个 tag 都是鸡肋，要么没用，要么常数大到不如 std 的，且有可能造成 MLE，故这里只推荐用默认的配对堆。同样，配对堆也优于 \texttt{algorithm} 库中的 \texttt{make\_heap()}。

\subsection{构造方式}

要注明命名空间因为和 std 的类名称重复。

\begin{minted}{text}
__gnu_pbds ::priority_queue<int> __gnu_pbds::priority_queue<int, greater<int> >
__gnu_pbds ::priority_queue<int, greater<int>, pairing_heap_tag>
__gnu_pbds ::priority_queue<int>::point_iterator id; // 迭代器
// 迭代器是一个内存地址，在modify和push的时候都会返回一个迭代器，下文会详细的讲使用方法
id = q.push(1);
\end{minted}

\subsection{成员函数}

\begin{enumerate}
\item \texttt{push()}: 向堆中压入一个元素, 返回该元素位置的迭代器
\item \texttt{pop()}: 将堆顶元素弹出
\item \texttt{top()}: 返回堆顶元素
\item \texttt{size()}返回元素个数
\item \texttt{empty()}返回是否非空
\item \texttt{modify(point\_iterator, const key)} : 把迭代器位置的 key 修改为传入的 key，并对底层储存结构进行排序
\item \texttt{erase(point\_iterator)} : 把迭代器位置的键值从堆中擦除
\item \texttt{join(\_\_gnu\_pbds :: priority\_queue \&other)}: 把 other 合并到  this 并把 other 清空。
\end{enumerate}

使用的 \texttt{tag} 决定了每个操作的时间复杂度：

\begin{tabular}{cclccc}
\hline
 & push& pop& modify& erase& Join\\Pairing\_heap\_tag& O(1)& 最坏& 最坏& 最坏& O(1)\\Binary\_heap\_tag& 最坏& 最坏& \textbackslash{}Theta(n)& \textbackslash{}Theta(n)& \textbackslash{}Theta(n)\\Binomial\_heap\_tag& 最坏& \textbackslash{}Theta(\textbackslash{}log(n))& \textbackslash{}Theta(\textbackslash{}log(n))& \textbackslash{}Theta(\textbackslash{}log(n))& \textbackslash{}Theta(\textbackslash{}log(n))\\Rc\_Binomial\_heap\_tag& O(1)& \textbackslash{}Theta(\textbackslash{}log(n))& \textbackslash{}Theta(\textbackslash{}log(n))& \textbackslash{}Theta(\textbackslash{}log(n))& \textbackslash{}Theta(\textbackslash{}log(n))\\Thin\_heap\_tag& O(1)& 最坏& 最坏& 最坏& \textbackslash{}Theta(n)\\\hline
\end{tabular}

\subsection{示例}

\begin{cppcode}
#include <algorithm>
#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>
#include <iostream>
using namespace __gnu_pbds;
// 由于面向OIer, 本文以常用堆 : pairing_heap_tag作为范例
// 为了更好的阅读体验，定义宏如下 ：
#define pair_heap __gnu_pbds ::priority_queue<int>
pair_heap q1;  //大根堆, 配对堆
pair_heap q2;
pair_heap ::point_iterator id;  // 一个迭代器
int main() {
  id = q1.push(1);
  // 堆中元素 ： [1];
  for (int i = 2; i <= 5; i++) q1.push(i);
  // 堆中元素 :  [1, 2, 3, 4, 5];
  std ::cout << q1.top() << std ::endl;
  // 输出结果 : 5;
  q1.pop();
  // 堆中元素 : [1, 2, 3, 4];
  id = q1.push(10);
  // 堆中元素 : [1, 2, 3, 4, 10];
  q1.modify(id, 1);
  // 堆中元素 :  [1, 1, 2, 3, 4];
  std ::cout << q1.top() << std ::endl;
  // 输出结果 : 4;
  q1.pop();
  // 堆中元素 : [1, 1, 2, 3];
  id = q1.push(7);
  // 堆中元素 : [1, 1, 2, 3, 7];
  q1.erase(id);
  // 堆中元素 : [1, 1, 2, 3];
  q2.push(1), q2.push(3), q2.push(5);
  // q1中元素 : [1, 1, 2, 3], q2中元素 : [1, 3, 5];
  q2.join(q1);
  // q1中无元素，q2中元素 ：[1, 1, 1, 2, 3, 3, 5];
}
\end{cppcode}
